package com.sise.DP;

/**
 *      0-1 背包问题
 *      给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。
 *      其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
 *
 *      题解：
 *      1、状态：状态会随着 选择而改变。故此有多少个变化量，就有多少个状态，在此题有两个变量，所以为 dp[][] 二维数组
 *          1.1 背包的空余容量剩多少
 *          1.2 可选择的物品还有哪些
 *      2、选择：
 *          2.1 把这个物品装进背包
 *          2.2 不把这个物品装进背包
 *
 *      3、模板如下：
 *
 *      # 初始化 base case
 *      dp[0][0][...] = base
 *      # 进行状态转移
 *      for 状态1 in 状态1的所有取值：
 *          for 状态2 in 状态2的所有取值：
 *              for ...
 *                  dp[状态1][状态2][...] = 求最值(选择1，选择2...)
 *
 *      4、dp[i][w] 的含义为对于前 i 个物品，当背包容量为 w 时，可以装的最大价值是 dp[i][w]
 */
public class _01Knapsack {
    public int knapsack(int W, int N, int[] wt, int[] val) {

        // base case
        int[][] dp = new int[N + 1][W + 1];

        // 由于这里的初始化 base case，故此下面的 wt[]，val[] 获取第 i 个物品、价值时，都需要进行 -1 操作
        // dp[0][..] = 0;    // 如果为 0 个物品，那么价值一定为 0
        // dp[..][0] = 0;    // 如果背包容量为 0，那么价值也为 0

        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= W; w++) {

                if (w - wt[i - 1] < 0) {            // 如果超过剩余容量，那么就只能选择不装进背包
                    dp[i][w] = dp[i - 1][w];
                } else {
                    dp[i][w] = Math.max(            // 装进或者不装进背包，择优

                            // 1、把第 i 个物品装进背包，dp[i - 1][w - wt[i - 1]] 取得 w 容量需要变化，参考第4点，dp[][]的原始含义。
                            // 在 w - wt[i - 1] 的容量中取得最大价值，再加上当前第 i 个物品的价值 val，就得到了 dp[][] 的价值
                            // 小细节：由于 wt[]、val[] 索引从零开始，初始化留给了base case，而我们循环从 1 开始，故此需要写成 wt[i - 1]、val[i - 1]
                            dp[i - 1][w - wt[i - 1]] + val[i - 1],

                            // 2、不把第 i 个物品装进背包，和前一个不放物品的 dp[i-1][w] 总价值相同
                            dp[i - 1][w]
                    );
                }
            }
        }
        return dp[N][W];
    }
}
